The invention relates generally to queuing of received data units in networking devices, and more specifically to a system for temporarily storing and dequeuing received data units for subsequent transmission based on their relative priorities and the availability of transmit credits.
A network switch is one example of the many types of networking devices used to interconnect computer and/or communications networks ("networks"). These devices receive and forward data units such as cells, packets, messages or frames from other devices located within one or more networks to which they are connected. For example, a network switch may be used to forward data units between networks employing a variety of communications protocols, such as Asynchronous Transfer Mode (ATM) or Frame Relay. Such devices typically include some amount of buffer memory to store data units as they are received, together with some combination of hardware circuits and/or software-implemented functionality.
During operation of a network switch, conditions may arise which require it to store received data units for some period of time before they can be transmitted from the device. For example, one or more output links of the device may become congested due to a lack of available transmission bandwidth. In such situations, the stored data units should be organized and forwarded to their respective output links in such a way that their relative priorities are maintained. For example, the priority of a data unit associated with a virtual connection may be indicated by a specific Quality of Service (QoS) indicating levels of delay and loss sensitivity associated with the connection. QoS parameters for a connection may include a guaranteed level of bandwidth, sometimes referred to as a Committed Information Rate (CIR), and an available bandwidth level, sometimes referred to as an Excess Information Rate (EIR). A data unit associated with the CIR of a connection is considered to have priority over a data unit associated with the EIR of that connection or another connection. This relative priority between received data units should be maintained in the way data units are temporarily stored in a device as a result of output link congestion, and in any protocol used to forward such stored data units for subsequent transmission.
The originator of a frame in a frame relay network may expressly indicate a frame's priority by selecting a value of a "discard enabled" (DE) bit contained in the frame. Network switches receiving a frame with the DE bit set are permitted to discard the frame in the face of congestion at an outbound link. Accordingly, a frame with the DE bit set may have a lower priority with respect to other frames with the DE bit clear. This type of relative priority between received data units should also be maintained in the way they are temporarily stored in a network switch as a result of output link congestion, and in any protocol used to subsequently forward such data units for transmission.
Virtual connections passing through a network switch typically employ a flow control protocol, which controls when data units buffered at each node traversed by the virtual connection may be forwarded downstream. An example of a credit based flow control protocol providing QoS guarantees in an ATM environment is described in Quantum Flow Control, Version 2.0, published Jul. 25, 1995, available on the World Wide Web at http://www.qfc.org. The Quantum Flow Control (QFC) protocol requires a transmitting device to have received sufficient transmit credits from the next downstream node to transmit a complete frame before it can begin transmitting the frame to the downstream node. As frames are transmitted, the transmitting device logically decrements a transmit credit count. As the downstream node frees up buffers which can be used to receive more frames, it sends transmit credits upstream to the transmitter. By requiring a transmitter to accumulate sufficient credits to transmit a complete frame before it can begin transmitting that frame, QFC ensures that downstream buffers are available to store the frame. However, this requirement may also introduce undesirable or unacceptable delay to a frame.
For the reasons stated above it would be desirable to have a system for temporarily storing data units in a network device which maintains the relative priorities of the data units, for example as determined by their QoS levels and/or DE bit values. Such relative priorities should be maintained both in the manner in which the data units are stored, as well as in the manner in which they are forwarded to their respective output links. In addition, the system should provide flow control in a way that is consistent with the relative priorities of received data units.